package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author initcap
 * @date Created in 1/20/19 5:56 PM.
 */
public class Path {

    /**
     * 图的引用
     */
    private Graph<Integer, Double> g;
    /**
     * 记录dfs的过程中节点是否被访问
     */
    private boolean[] visited;
    /**
     * 记录路径, from[i]表示查找的路径上i的上一个节点
     */
    private int[] from;

    /**
     * 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
     *
     * @param graph 图的引用
     * @param s     顶点
     */
    public Path(Graph graph, int s) {

        // 算法初始化
        g = graph;
        g.validateVertex(s, g.nodeSize());

        visited = new boolean[g.nodeSize()];
        from = new int[g.nodeSize()];
        for (int i = 0; i < g.nodeSize(); i++) {
            visited[i] = false;
            from[i] = -1;
        }

        // 寻路算法
        dfs(s);
    }

    /**
     * 图的深度优先遍历
     *
     * @param v
     */
    private void dfs(int v) {
        visited[v] = true;
        for (int i : g.adj(v)) {
            if (!visited[i]) {
                from[i] = v;
                dfs(i);
            }
        }
    }

    /**
     * 查询从s点到w点是否有路径
     *
     * @param w
     * @return
     */
    private boolean hasPath(int w) {
        g.validateVertex(w, g.nodeSize());
        return visited[w];
    }

    /**
     * 查询从s点到w点的路径, 存放在vec中
     *
     * @param w
     * @return
     */
    List<Integer> path(int w) {

        assert hasPath(w);

        Deque<Integer> s = new ArrayDeque<>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while (p != -1) {
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        List<Integer> res = new ArrayList<>();
        while (!s.isEmpty()) {
            res.add(s.pop());
        }

        return res;
    }

    /**
     * 打印出从s点到w点的路径
     *
     * @param w
     */
    void showPath(int w) {

        assert hasPath(w);

        List<Integer> list = path(w);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
            if (i == list.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

}
